package com.lmk.dsa.struct.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import com.lmk.dsa.struct.commons.Edge;

/**
 * 带权图抽象类
 * @author LaoMake
 * @since 1.0
 */
public abstract class Graph {

	/** 是否为有向图 */
	protected boolean directed = false;

	/** 顶点的总数 */
	protected int n;

	/** 边的总数 */
	protected int m;

	/** 顶点列表 */
	protected List<Object> vertexList;

	/** 边列表 */
	protected List<Edge> edgeList;


	/**
	 * 只提供这一个带参的构造器
	 * 必须在初始化的时候确定顶点总数
	 * @param n
	 */
	public Graph(int n) {
		this.n = n;
		this.m = 0;
		vertexList = new ArrayList<>(n);
		edgeList = new ArrayList<>(n - 1);
	}

	/**
	 * 通过数组初始化图
	 * @param vertexes 顶点
	 */
	public Graph(Object... vertexes) {
		this.n = vertexes.length;
		vertexList = Arrays.asList(vertexes);
		edgeList = new ArrayList<>();
	}

	public boolean isDirected() {
		return directed;
	}

	public void setDirected(boolean directed) {
		this.directed = directed;
	}

	/**
	 * 获取边的总数
	 * @return
	 */
	public int edgeSize() {
		return this.m;
	}

	/**
	 * 获取顶点总数
	 * @return
	 */
	public int vertexSize() {
		return this.n;
	}
	
	/**
	 * 获取节点列表
	 * @return
	 */
	public List<Object> getVertexList(){
		return this.vertexList;
	}

	/**
	 * 根据指定索引获取顶点信息
	 * @param index
	 * @return
	 */
	public Object getVertex(int index){
		return this.vertexList.get(index);
	}

	/**
	 * 根据顶点索引获取其所有邻边
	 * @param index
	 * @return
	 */
	public abstract List<Edge> adjoinEdge(int index);

	/**
	 * 根据顶点索引获取其相邻节点索引列表
	 * @param index
	 * @return
	 */
	public abstract List<Integer> adjoinVertex(int index);

	/**
	 * 获取边列表
	 * @return
	 */
	public List<Edge> getEdgeList(){
		return this.edgeList;
	}
	
	/**
	 * 添加顶点
	 * @param v
	 */
	public void addVertex(Object v) {
		assert n > vertexList.size() : "顶点集合已满";
		
		vertexList.add(v);
	}
	
	/**
	 * 添加边，默认权值为：1
	 * @param from	起始顶点索引
	 * @param to	目标顶点索引
	 */
	public void addEdge(int from, int to) {
		addEdge(from, to, 1);
	}
	
	/**
	 * 添加边
	 * @param from	起始顶点索引
	 * @param to	目标顶点索引
	 * @param weight	权值
	 */
	public abstract void addEdge(int from, int to, int weight);
	
	/**
	 * 返回v1, v2的权值
	 * @param v1
	 * @param v2
	 * @return
	 */
	public abstract Integer weight(int v1, int v2);
	
	/**
	 * 判断v1, v2之间是否存在边
	 * @param v1
	 * @param v2
	 * @return
	 */
	public abstract boolean hasEdge(int v1, int v2);
	
	/**
	 * 打印边的信息
	 */
	public abstract void show();
}
